package ahu.zdw.com;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/5/2 21:39
 */
public class Test5 {
    public static void main(String[] args) {
        String haystack = "abeababeabf", needle = "abeabf";
//        String haystack = "abeababeabf", needle = "aaaa";
        System.out.println(strStr(haystack, needle));
    }

    public static int strStr1(String haystack, String needle){
        int n = haystack.length(), m = needle.length();
        char[] ha = haystack.toCharArray();
        char[] ne = needle.toCharArray();
        for (int i = 0; i <= n-m; i++){
            int a = i, b = 0;
            while (b < m && ha[a]==ne[b]){
                a++;
                b++;
            }
            if (b==m) return i;
        }
        return -1;
    }

    public static int strStr(String haystack, String needle){
        if (needle.isEmpty()) return 0;
        int n = haystack.length(), m = needle.length();
        haystack = " " + haystack;
        needle = " " + needle;
        char[] ha = haystack.toCharArray();
        char[] ne = needle.toCharArray();

        int[] next = new int[m+1];
        for (int i = 2, j = 0; i <= m; i++){
            while (j > 0 && ne[i] != ne[j+1]) j = next[j];
            if (ne[i] == ne[j+1]) j++;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= n; i++){
            while (j > 0 && ha[i] != ne[j+1]) j = next[j];
            if (ha[i] == ne[j+1]) j++;
            if (j == m) return i - m;
        }
        return -1;
    }
}
